package cn.chen.算法.排序;

import java.util.Arrays;

/**
 * 插入排序
 * 每次从无序表中拿出第一个，与有序表进行比较，从右往左比较，如果逆序，就将有序表比较的元素向后移，直到找到合适的位置将该元素插入进去
 * */
public class InsertionSort {

    public static void main(String[] args){

        int[] arr={51,1,2,-4,8,0};

        System.out.println(Arrays.toString(arr));
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr){

        // 临时存储无序表的第一个元素
        int temp=0;
        for(int i=1;i< arr.length;i++){

            temp=arr[i];
            for(int j=i-1;j>=0;j--){    // 从右往左遍历有序表

                if(arr[j]>temp){

                    arr[j+1]=arr[j];    // 将有序表的元素后移
                    arr[j]=temp;        // 将值复制到有序表中
                }
            }
        }
    }
    // 该方法与上面方法一样，只是循环不同
    public static void insertionSort1(int[] arr){

        // 临时存储无序表的第一个元素
        int temp=0,j;
        for(int i=1;i< arr.length;i++){

            temp=arr[i];
            j=i-1;
            while(j>=0&&arr[j]>temp){

                arr[j+1]=arr[j];    // 将有序表的元素后移
                arr[j]=temp;        // 将值复制到有序表中
                j--;
            }
        }
    }
}
